"""
题目：https://leetcode-cn.com/problems/merge-k-sorted-lists/
    给你一个链表数组，每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中，返回合并后的链表。

    示例 1：
    输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
    1->4->5,
    1->3->4,
    2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6
思路：先设置输出ans为None(注意一定要是None,否则会报执行错误的bug)，然后将ans与输入中的每一个链表合并，直到最后
时间复杂度：O(k^2 * n)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ans = None
        for lst in lists:
            ans = self.merge2Lists(ans,lst)
        return ans if len(lists) > 0 else None
        

    def merge2Lists(self,l1,l2):
        # if not l2:
        #     return l1
        # if not l1:
        #     return l2
        head = ListNode(-1)
        pre = head
        while l1 and l2:
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next
        if l1 is None:
            pre.next = l2
        if l2 is None:
            pre.next = l1
        
        return head.next